package cxydmmszl.tmp.t9;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 邮局选址问题
 * <li style="color: green;">Desc</li>
 * 一条直线上有居民点，邮局只能建在居民点上。给定一个有序整形数组 arr，
 * 每个值表示居民点的一维坐标，再给定一个正数 num，表示邮局数量。
 * 选择 num 个居民点建立 num 个邮局，使所有的居民点到邮局的总距离最短，返回最短的总距离。
 * <br/><br/>备注：<br/>
 * 1⩽N⩽3000<br/>
 * 1⩽num⩽N<br/>
 * 1⩽邮局坐标⩽10000
 * <li style="color: green;">Input</li>
 * 第一行有两个整数 N,num。分别表示居民点的数量，要建的邮局数量。<br/>
 * 接下来一行 N 个整数表示邮局的坐标。保证坐标递增
 * <li style="color: green;">Output</li>
 * 输出一个整数表示答案
 * <li style="color: blue;">Link</li> CD90
 *
 * @author habitplus
 * @since 2021-11-18 14:50
 */
public class Main {
    private static final StreamTokenizer ST = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            ST.nextToken();
            return (int) ST.nval;
        } catch (IOException e) {
            throw new RuntimeException("Input Error!");
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int num = nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        int ans = minDistance2(arr, num);
        System.out.println(ans);
    }

    private static int minDistance1(int[] arr, int num) {
        if (arr == null || arr.length < 1 || num > arr.length)
            return 0;
        int n = arr.length;
        int[][] w = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                w[i][j] = w[i][j - 1] + arr[j] - arr[(i + j) / 2];
            }
        }

        int[][] dp = new int[num][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = w[0][i];
        }

        for (int i = 1; i < num; i++) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k <= j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + w[k + 1][j]);
                }
            }
        }
        return dp[num - 1][n - 1];
    }

    private static int minDistance2(int[] arr, int num) {
        if (arr == null || arr.length < 1 || num > arr.length)
            return 0;
        int n = arr.length;
        int[][] w = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                w[i][j] = w[i][j - 1] + arr[j] - arr[(i + j) / 2];
            }
        }

        int[][] dp = new int[num][n];
        int[][] s = new int[num][n];

        for (int i = 0; i < n; i++) {
            dp[0][i] = w[0][i];
            s[0][i] = 0;
        }

        int minK = 0;
        int maxK = 0;
        int cur = 0;
        for (int i = 1; i < num; i++) {
            for (int j = n - 1; j > i; j--) {
                minK = s[i - 1][j];
                maxK = j == arr.length - 1 ? arr.length - 1 : s[i][j + 1];
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = minK; k <= maxK; k++) {
                    cur = dp[i - 1][k] + w[k + 1][j];
                    if (cur <= dp[i][j]) {
                        dp[i][j] = cur;
                        s[i][j] = k;
                    }
                }
            }
        }
        return dp[num - 1][n - 1];
    }
}
